package leetcode_tag.树;

//二叉搜索树种类只与长度有关，与具体的数字无关
public class LeetCode96 {

    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int sum = 0;
            //j表示起始位置
            for (int j = 1; j <= i; j++) {
                // 左子树*右子树
                sum += dp[j - 1] * dp[i - j];
            }
            dp[i] = sum;
        }
        return dp[n];
    }

    // 递归超出时间复杂度  长度有多少种树 1-3 5种  4-7 5种
//    private int helper(int start, int end) {
//        if (start > end)
//            return 1;
//        int sum = 0;
//        for (int i = start; i <= end; i++) {
//            int left = helper(start, i - 1);
//            int right = helper(i + 1, end);
//            sum += left * right;
//        }
//        return sum;
//    }
}
